<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>
  <body>
    <script>
      function merge(left, right) {
        let tem = [];
        while (left.length && right.length) {
          if (left[0] < right[0]) {
            tem.push(left.shift());
          } else {
            tem.push(right.shift());
          }
        }
        return tem.concat(left, right);
      }

      function mergeSort(arr) {
        const len = arr.length;
        if (len < 2) return arr;
        let mid = Math.floor(len / 2),
          left = arr.slice(0, mid),
          right = arr.slice(mid);
        // 先分再合
        return merge(mergeSort(left), mergeSort(right));
      }
      console.log(mergeSort([1, 4, 5, 7, 8, 9, 6, 100, 99]));
    </script>
  </body>
</html>
